package LeetCode.Leet700_799.Leet730_739.Leet738;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/6/8 20:29
 * @Description TODO: 方法一   递归（贪心）  1ms 94.50%
 *                  递减处元素值减1，后面元素均置为9，然后递归求解
 */
class Solution_1 {
    int[] num;

    public int monotoneIncreasingDigits(int n) {
        if (n == 0) {
            return 0;
        }
        // 整数为int数组，方便求解
        List<Integer> list = new ArrayList<>();
        while (n != 0) {
            list.add(n % 10);
            n = n / 10;
        }
        int len = list.size();
        num = new int[len];
        for (int i = 0; i < len; i++) {
            num[i] = list.get(len - i - 1);
        }

        // 求解
        domonotoneIncreasingDigits();

        // 数组转整数
        int result = 0;
        for (int i = 0; i < len; i++) {
            result *= 10;
            result += num[i];
        }

        return result;
    }

    public void domonotoneIncreasingDigits() {
        // 如果为单调递增整数，答案即为这个
        // 如果不是，则找到第一个单调递减的位置，该位置处元素值减1，并且将该位置后面的元素均置为9，然后递归寻找答案
        int i;
        for (i = 1; i < num.length; i++) {
            if (num[i] < num[i - 1]) {
                break;
            }
        }
        // i - 1处元素减1，后面元素变为9，递归寻找答案
        if (i != num.length) {
            num[i - 1]--;
            while (i < num.length) {
                num[i++] = 9;
            }
            domonotoneIncreasingDigits();
        }

        return;
    }
}
